Verižni seznam

Vozel

1. podnaloga

Razred Vozel predstavlja osnovni gradnik verižnega seznama. Pri tej nalogi bomo dodali razredu Vozel nekaj novih metod. Za osnovno vzemite naslednjo implementacijo:

class Vozel:
    """
    Osnovni sestavni del verižnega seznama.
    """

    def __init__(self, podatek=None, naslednji=None):
        self.podatek = podatek
        self.naslednji = naslednji

    def __str__(self):
        return str(self.podatek)

Razredu Vozel dodajte metodo vrni_seznam(self), ki vrne seznam vseh podatkov v verižnem seznamu. Zgled:

>>> v1 = Vozel('nedelja')
>>> v2 = Vozel('sobota', v1)
>>> v3 = Vozel('petek', v2)
>>> v3.vrni_seznam()
['petek', 'sobota', 'nedelja']

Uradna rešitev

class Vozel:
    """
    Osnovni sestavni del verižnega seznama.
    """

    def __init__(self, podatek=None, naslednji=None):
        self.podatek = podatek
        self.naslednji = naslednji
    
    def __str__(self):
        return str(self.podatek)

    def vrni_seznam(self):
        """
        Vrni seznam s podatki, ki so shranjeni v vozlih.
        """
        sez = []
        p = self
        while p is not None:
            sez.append(p.podatek)
            p = p.naslednji
        return sez

2. podnaloga

Razredu Vozel dodajte metodo dodaj_na_zacetek(self, x), ki doda nov vozel na začetek verižnega seznama self, ter vrne referenco na novi vozel. Zgled:

>>> v = Vozel('nedelja')
>>> v = v.dodaj_na_zacetek('sobota')
>>> v = v.dodaj_na_zacetek('petek')
>>> v.vrni_seznam()
['petek', 'sobota', 'nedelja']

Uradna rešitev

class Vozel(Vozel):
    
    def dodaj_na_zacetek(self, x):
        """
        Dodaj nov vozel na začetek verižnega seznama.
        """
        return Vozel(x, self)

3. podnaloga

Razredu Vozel dodajte metodo dodaj_na_konec(self, x), ki doda nov vozel na konec verižnega seznama self. Zgled:

>>> v = Vozel('petek')
>>> v.dodaj_na_konec('sobota')
>>> v.dodaj_na_konec('nedelja')
>>> v.vrni_seznam()
['petek', 'sobota', 'nedelja']

Uradna rešitev

class Vozel(Vozel):
    
    def dodaj_na_konec(self, x):
        """
        Dodaj nov vozel na konec verižnega seznama.
        """
        p = self
        while p.naslednji != None:
            p = p.naslednji
        p.naslednji = Vozel(x)

4. podnaloga

Razredu Vozel dodajte metodo __len__(self), ki vrne število vozlov v verižnem seznamu. Zgled:

>>> v = Vozel('sobota')
>>> v.dodaj_na_konec('nedelja')
>>> v = v.dodaj_na_zacetek('petek')
>>> len(v)
3

Uradna rešitev

class Vozel(Vozel):
    
    def __len__(self):
        """
        Vrni število vozlov v verižnem seznamu.
        """
        if self.naslednji is None:
            return 1
        return 1 + len(self.naslednji)

5. podnaloga

Dodali bomo še nekaj funkcij za delo z verižnimi seznami.

Sestavite funkcijo stevilska_veriga(a, b), ki vrne verižni seznam, ki vsebuje števila od a do b. Funkcija naj vrne referenco na prvi vozel. Predpostavite, da velja a <= b. Zgled:

>>> v = stevilska_veriga(3, 7)
>>> v.vrni_seznam()
[3, 4, 5, 6, 7]

Uradna rešitev

def stevilska_veriga(a, b):
    """
    Vrni verižni seznam, ki vsebuje vsa števila od a do b.
    """
    if a == b:
        return Vozel(a)
    return Vozel(a, stevilska_veriga(a + 1, b))

6. podnaloga

Sestavite funkcijo seznam_sodih(vozel), ki kot argument dobil referenco na vozel in vrne seznam z vsemi sodimi elementi v tem verižnem seznamu. Predpostavite lahko, da so vsi podatki cela števila. Zgled:

>>> v = stevilska_veriga(3, 11)
>>> seznam_sodih(v)
[4, 6, 8, 10]

Uradna rešitev

def seznam_sodih(vozel):
    """
    Vrni seznam vseh sodih elementov v verižnem seznamu.
    """
    l = []
    while vozel is not None:
        if vozel.podatek % 2 == 0:
            l.append(vozel.podatek)
        vozel = vozel.naslednji
    return l

7. podnaloga

Sestavite funkcijo iz_seznama(l), ki kor argument sprejme seznam l ter vrne verižni seznam, ki kot podatke vsebuje elemente seznama l. Funkcija naj vrne referenco na prvi vozel. Predpostavite lahko, da je seznam l neprazen. Zgled:

>>> v = iz_seznama(['torek', 'sreda', 'četrtek', 'petek'])
>>> v.dodaj_na_konec('sobota')
>>> v.vrni_seznam()
['torek', 'sreda', 'četrtek', 'petek', 'sobota']

Uradna rešitev

def iz_seznama(l):
    """
    Vrni verižni seznam, ki bo imel kot podatke elemente seznama l.
    """
    prvi = Vozel(l[0])
    p = prvi
    for i in range(1, len(l)):
        p.naslednji = Vozel(l[i])
        p = p.naslednji
    return prvi

8. podnaloga

Razredu Vozel dodajte metodo zadnji_vozel(self), ki vrne referenco na zadnji vozel v verižnem seznamu. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'petek', 'sobota'])
>>> z = v.zadnji_vozel()
>>> print(z)
'sobota'

Uradna rešitev

class Vozel(Vozel):
    
    def zadnji_vozel(self):
        p = self
        while p.naslednji is not None:
            p = p.naslednji
        return p

9. podnaloga

Razredu Vozel dodajte metodo vstavi_na_mesto(self, n, x), ki dobi število n in podatek x. Metoda naj na n-to mesto v verižni seznam vstavi nov vozel s podatkom x. Funkcija naj vrne referenco na prvi vozel v verižnem seznamu. Če verižni seznam ni dovolj dolg, dodajte ustrezno število vozlov, ki imajo kot podatek None. Zgled:

>>> v = iz_seznama(['sreda', 'četrtek', 'sobota'])
>>> v = v.vstavi_na_mesto(2, 'petek')
>>> v.vrni_seznam()
['sreda', 'četrtek', 'petek', 'sobota']

Uradna rešitev

class Vozel(Vozel):

    def vstavi_na_mesto(self, n, x):
        if n == 0:
            return self.dodaj_na_zacetek(x)
        if self.naslednji == None:
            if n == 1:
                self.naslednji = Vozel(x)
                return self
            else:
                self.naslednji = Vozel()
        self.naslednji = self.naslednji.vstavi_na_mesto(n - 1, x)
        return self

Še o vozlih

1. podnaloga

Razred Vozel predstavlja osnovni gradnik verižnega seznama. Pri tej nalogi bomo dodali razredu Vozel nekaj novih metod. Za osnovno vzemite naslednjo implementacijo:

class Vozel:
    """
    Osnovni sestavni del verižnega seznama.
    """

    def __init__(self, podatek=None, naslednji=None):
        self.podatek = podatek
        self.naslednji = naslednji

    def __str__(self):
        return str(self.podatek)

Dodajte še funkcijo iz_seznama, ki ste jo sestavili pri prejšnji nalogi in metodo vrni_seznam. Če želite, lahko dodate še kakšno metodo oz. funkcijo.

Razredu Vozel dodajte metodo podvoji_verigo(self), ki naj sestavi in vrne novo kopijo verige, stare pa naj ne spreminja. Zgled:

>>> v = iz_seznama([2, 3, 4, 5])
>>> v2 = v.podvoji_verigo()
>>> v2.podatek = 11
>>> v.vrni_seznam()
[2, 3, 4, 5]
>>> v2.vrni_seznam()
[11, 3, 4, 5]

Uradna rešitev

class Vozel:
    """
    Osnovni sestavni del verižnega seznama.
    """

    def __init__(self, podatek=None, naslednji=None):
        self.podatek = podatek
        self.naslednji = naslednji

    def __str__(self):
        return str(self.podatek)
    
    def vrni_seznam(self):
        """
        Vrni seznam s podatki, ki so shranjeni v vozlih.
        """
        sez = []
        p = self
        while p is not None:
            sez.append(p.podatek)
            p = p.naslednji
        return sez


def iz_seznama(l):
    """
    Vrni verižni seznam, ki bo imel kot podatke elemente seznama l.
    """
    if not l: # če je seznam prazen
        return None
    prvi = Vozel(l[0])
    p = prvi
    for i in range(1, len(l)):
        p.naslednji = Vozel(l[i])
        p = p.naslednji
    return prvi


class Vozel(Vozel):
    
    def podvoji_verigo(self):
        if self.naslednji is None:
            return Vozel(self.podatek)
        return Vozel(self.podatek, self.naslednji.podvoji_verigo())

2. podnaloga

Sestavite funkcijo stakni_verigi(v1, v2), ki kot argumenta prejme referenci na dva vozla in sestavi novo verigo, ki jo dobi tako, da stakne obe verigi. To pomeni, da morata ostati verigi v1 in v2 nespremenjeni, funkcija pa vrne povsem novo verigo! Na primer:

>>> v1 = iz_seznama([1, 2, 3])
>>> v2 = iz_seznama([4, 5, 6])
>>> v = stakni_verigi(v1, v2)
>>> v.vrni_seznam()
[1, 2, 3, 4, 5, 6]
>>> v1.vrni_seznam()
[1, 2, 3]

Uradna rešitev

def stakni_verigi(v1, v2):
    '''Iz verig v1 in v2 naredi novo verigo.
       Prvotni ostaneta nespremenjeni! '''
    v = v1.podvoji_verigo() # nova, podvojena veriga
    # postavimo se na konec nove
    p = v
    while p.naslednji is not None:
        p = p.naslednji
    # in tej verigi dodamo kopijo verige v2
    p.naslednji = v2.podvoji_verigo()
    return v

def stakni_verigi(v1, v2):
    ''' "Grša oblika"
       Iz verig v1 in v2 naredi novo verigo.
       Prvotni ostaneta nespremenjeni! '''
    s1 = v1.vrni_seznam()
    s2 = v2.vrni_seznam()
    return iz_seznama(s1 + s2)

3. podnaloga

Sestavite funkcijo multipliciraj_verigo(v, n), ki kot argumenta prejme referenco na vozel in naravno število n ter vrne verigo spremeni, tako da iz vsakega vozla naredi n zaporednih kopij. Funkcija naj vrne referenco na prvi vozel. Na primer:

>>> v = iz_seznama([7, 5, 2])
>>> v = multipliciraj_verigo(v, 3)
>>> v.vrni_seznam()
[7, 7, 7, 5, 5, 5, 2, 2, 2]

Uradna rešitev

def multipliciraj_verigo(v, n, k=None):
    if v is None:
        return None
    if k is None:
        k = n
    if k == 1:
        v.naslednji = multipliciraj_verigo(v.naslednji, n)
        return v
    v2 = Vozel(v.podatek, multipliciraj_verigo(v, n, k-1))
    return v2

4. podnaloga

Sestavite funkcijo na_zadrgo(v1, v2), ki kot argumenta prejme referenci na dva vozla. Funkcija naj vrne verigo, ki jo dobi tako, da "na zadrgo" združi obe verigi. Funkcija naj vrne referenco na prvi vozel tako dobljene verige. Na primer:

>>> v1 = iz_seznama([7, 5, 2])
>>> v2 = iz_seznama([1, 3, 4, 9, 8])
>>> v = na_zadrgo(v1, v2)
>>> v.vrni_seznam()
[7, 1, 5, 3, 2, 4, 9, 8]

Uradna rešitev

def na_zadrgo(v1, v2):
    if v1 is None:
        return v2
    if v2 is None:
        return v1
    v = na_zadrgo(v1.naslednji, v2.naslednji)
    v1.naslednji = v2
    v2.naslednji = v
    return v1

5. podnaloga

Sestavite funkcijo odpni_zadrgo(v), ki kot argument prejme referenco na vozel ter vrne dve verigi, ki jih dobi tako, da "odpne zadrgo", tj. vozle naj razdeli med dve verigi. Funkcija naj vrne par in sicer referenci na začetna vozla v obeh verigah. Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v1, v2 = odpni_zadrgo(v)
>>> v1.vrni_seznam()
[7, 2, 3, 9]
>>> v2.vrni_seznam()
[5, 1, 4, 8]

Uradna rešitev

def odpni_zadrgo(v):
    if v is None:
        return None, None
    vn = v.naslednji
    if vn is None:
        return v, None
    v1, v2 = odpni_zadrgo(v.naslednji.naslednji)
    v.naslednji = v1
    vn.naslednji = v2
    return v, vn

6. podnaloga

Sestavite funkcijo odstrani(v, x), ki kot argumenta prejme referenco na vozel ter element x. Funkcija naj verigo popravi, tako da odstrani vozle, ki kot podatek vsebujejo element x. Funkcija naj vrne referenco na začetni vozel verige. Na primer:

>>> v = iz_seznama([7, 5, 2, 5, 3, 5])
>>> v = odstrani(v, 5)
>>> v.vrni_seznam()
[7, 2, 3]

Uradna rešitev

def odstrani(v, x):
    if v is None:
        return None
    if v.podatek != x:
        v.naslednji = odstrani(v.naslednji, x)
        return v
    return odstrani(v.naslednji, x)

7. podnaloga

Sestavite funkcijo sodi_in_lihi(v), ki kot argument prejme referenco na vozel ter vrne dve verigi, ki jih dobi tako, da v eno zloži vozle, ki vebujejo sode podatke, v drugo pa vozle, ki vsebujejo lihe podatke. Funkcija naj vrne par in sicer referenci na začetna vozla v obeh verigah. Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v1, v2 = sodi_in_lihi(v)
>>> v1.vrni_seznam()
[2, 4, 8]
>>> v2.vrni_seznam()
[7, 5, 1, 3, 9]

Uradna rešitev

def sodi_in_lihi(v):
    if v is None:
        return None, None
    v1, v2 = sodi_in_lihi(v.naslednji)
    if v.podatek % 2 == 0:
        v.naslednji = v1
        return v, v2
    v.naslednji = v2
    return v1, v

8. podnaloga

Razredu Vozel dodajte metodo je_urejen(self), ki vrne True, če je verižni seznam urejen naraščajoče in False, če ni. Zgled:

>>> v = iz_seznama([1, 2, 4, 7, 8])
>>> v.je_urejen()
True
>>> v = iz_seznama([1, 2, 4, 3, 7])
>>> v.je_urejen()
False

Uradna rešitev

class Vozel(Vozel):

    def je_urejen(self):
        if self.naslednji is None:
            return True
        if self.podatek > self.naslednji.podatek:
            return False
        return self.naslednji.je_urejen()

9. podnaloga

Razredu Vozel dodajte metodo vstavi_v_urejenega(self, x), ki podatek x vstavi na primerno mesto v verižni seznam. Predpostavka je, da je verižni seznam urejen. Metoda naj vrne začetni vozel tega verižnega seznama. Zgled:

>>> v = iz_seznama([1, 2, 4, 7, 8])
>>> v = v.vstavi_v_urejenega(3)
>>> v.vrni_seznam()
[1, 2, 3, 4, 7, 8]

Uradna rešitev

class Vozel(Vozel):

    def vstavi_v_urejenega(self, x):
        if x <= self.podatek:
            v = Vozel(x, self)
            return v
        if self.naslednji is None:
            self.naslednji = Vozel(x)
        else:
            self.naslednji = self.naslednji.vstavi_v_urejenega(x)
        return self

10. podnaloga

Sestavite funkcijo preuredi_parnost(v), ki kot argument prejme referenco na vozel ter verižni seznam tako preuredi, da postavi vse vozle, ki vsebujejo lih podatek na začetek, vozle, ki vsebujejo sod podatek pa na konec. Funkcija naj vrne par in sicer referenci na začetna vozla v obeh verigah. Na primer:

>>> v = iz_seznama([7, 5, 2, 1, 3, 4, 9, 8])
>>> v = preuredi_parnost(v)
>>> v.vrni_seznam()
[7, 5, 1, 3, 9, 2, 4, 8]

Uradna rešitev

def pripoji_verigo(v1, v2):
    p = v1
    while p.naslednji is not None:
        p = p.naslednji
    p.naslednji = v2
    return v1

def preuredi_parnost(v):
    s, l = sodi_in_lihi(v)
    return pripoji_verigo(l, s)

11. podnaloga

Pepi je sestavil verižni seznam in ugotovil, da je elemente nizal v seznam v napačnem vrstnem redu. Zdaj je treba seznam obrniti, tako da obstoječih vozlov ne brišemo in ne dodajamo novih. Sestavite funkcijo obrni_na_mestu(v), ki dobi verižni seznam in ga obrne na mestu. Funkcijo mora vrniti referenco na prvi vozel. Zgled:

>>> v = iz_seznama([7, 5, 2, 1])
>>> v = obrni_na_mestu(v)
>>> v.vrni_seznam()
[1, 2, 5, 7]

Uradna rešitev

def obrni_na_mestu(v):
    prejsnji = None
    while v is not None:
        nasl = v.naslednji
        v.naslednji = prejsnji
        prejsnji = v
        v = nasl
    return prejsnji

Izštevanka

1. podnaloga

Otroci se bodo igrali skrivalnice. Izbrati morajo nekoga, ki bo mižal, zato so se vsi postavili v krog. Uporabljajo zelo popularno izštevanko, ki ima n zlogov. Sestavite funkcijo kdo_mizi(imena, n), ki kot argument dobi seznam imen in naravno število n. Funkcija naj najprej sestavi krožni seznam (tako kot verižni seznam, samo da zadnji element kaže na prvega). Nato vozle izločamo iz kroga, tako da zbrišemo $n$-tega in začnemo ponovno izštevanje pri naslednjemu. Funkcija na vrne ime otroka, ki bo mižal. Zgled:

>>> kdo_mizi(['Mojca', 'Janez', 'Micka', 'Peter', 'Matjaž', 'Jožefa'], 5)
'Mojca'

Uradna rešitev

class Vozel:
    """
    Osnovni sestavni del verižnega seznama.
    """

    def __init__(self, podatek=None, naslednji=None):
        self.podatek = podatek
        self.naslednji = naslednji

    def __str__(self):
        return str(self.podatek)
    
    def vrni_seznam(self):
        """
        Vrni seznam s podatki, ki so shranjeni v vozlih.
        """
        sez = []
        p = self
        while p is not None:
            sez.append(p.podatek)
            p = p.naslednji
        return sez


def iz_seznama(l):
    """
    Vrni verižni seznam, ki bo imel kot podatke elemente seznama l.
    """
    prvi = Vozel(l[0])
    p = prvi
    for i in range(1, len(l)):
        p.naslednji = Vozel(l[i])
        p = p.naslednji
    return prvi

def kdo_mizi(imena, n):
    i = 0
    while len(imena) > 1:
        i = (i + n - 1) % len(imena)
        del imena[i]
    return imena[0]

2. podnaloga

Sestavite še funkcijo zgodovina_izstevanja(imena, n), ki naj deluje podobno kot funkcija iz prve podnaloge, le da vrne seznam, ki vsebuje imena v takem vrstnem redu, kot smo jih izločali pri izštevanki. Zgled:

>>> zgodovina_izstevanja(['Mojca', 'Janez', 'Micka', 'Peter', 'Matjaž', 'Jožefa'], 5)
['Matjaž', 'Peter', 'Jožefa', 'Janez', 'Micka', 'Mojca']

Uradna rešitev

def zgodovina_izstevanja(imena, n):
    i = 0
    ret = []
    while len(imena) > 0:
        i = (i + n - 1) % len(imena)
        ret.append(imena[i])
        del imena[i]
    return ret

3. podnaloga

Zdaj pa sestavite še funkcijo odhajanje_iz_kroga(imena, n), ki deluje podobno kot prejšnja funkcija, le da vrne verižni seznam namesto običajnega seznama. Vozli naj bodo urejeni tako, da je v zadnjem vozlu shranjeno ime otroka, ki je najprej zapustil krog. Zgled:

>>> v = odhajanje_iz_kroga(['Mojca', 'Janez', 'Micka', 'Peter', 'Matjaž', 'Jožefa'], 5)
>>> v.vrni_seznam()
['Mojca', 'Micka', 'Janez', 'Jožefa', 'Peter', 'Matjaž']

Uradna rešitev

def odhajanje_iz_kroga(imena, n):
    i = 0
    ret = []
    while len(imena) > 0:
        i = (i + n - 1) % len(imena)
        ret.append(imena[i])
        del imena[i]
    return iz_seznama(ret[::-1])